package binarytree

import "fmt"

// 最大二叉树

func Maximum(nums []int) *TreeNode {
	// 思路
	// 找到最大值及其位置index作为root节点
	// root.Left 重复该操作，只不过操作对象为 [:index]
	// root.Right 重复该操作，只不过操作对象为 [index+1:]
	if len(nums) == 0 {
		return nil
	}

	maxPos := findMaxPos(nums)
	root := &TreeNode{Val: nums[maxPos]}

	fmt.Printf("xxx: %d\n", nums[maxPos])

	root.Left = Maximum(nums[:maxPos])
	root.Right = Maximum(nums[maxPos+1:])

	return root
}

func findMaxPos(input []int) int {
	max := input[0]
	pos := 0
	for i := 0; i < len(input); i++ {
		if input[i] > max {
			pos = i
			max = input[i]
		}
	}
	return pos
}
